<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
    <meta http-equiv="Content-Style-Type" content="text/css" />
    <title>Assignments</title>
    <link href="/library/skin/tool_base.css" type="text/css" rel="stylesheet" media="all" />
<link href="/library/skin/gatech/tool.css" type="text/css" rel="stylesheet" media="all" />
<script type="text/javascript" language="JavaScript" src="/library/js/headscripts.js"></script>
	
    
    		<!-- vm/editor/FCKeditor/sakai_header.vm -->
	<script type="text/javascript" src="/library/editor/FCKeditor/fckeditor.js"></script>
    
  </head>
  <body  onload="setMainFrameHeight('Main21dea42cxf6e6x409exa1e3x4f69fd0b3088');setFocus(focus_path);"  >
<div class="portletBody">
														<h3>Assignment
																	<span class="highlight">
						 	- In progress
							</span>
										</h3>
																		<p class="instruction">
								 	Add attachment(s), then choose the appropriate button at the bottom.
							</p>	
						<table class="itemSummary"  summary="The assignment info">
				<tr>
					<th>
						Title
					</th>
					<td>
						Project 2: Barrier Synchronization
																	</td>
				</tr>
				<tr>
					<th>
						Due
					</th>
					<td>
						Oct 23, 2011 11:55 pm
					</td>
				</tr>
													<tr>
					<th>
						Status
					</th>
					<td>
													Not Started
											</td>
				</tr>
																			<tr>	
							<th>
								Grade Scale
							</th>
							<td>
								Points
																	(max 10.0)
															</td>
						</tr>
																						<tr>
						<th>
								Modified by instructor
						</th>
						<td>
							Oct 12, 2011 4:09 pm
						</td>
					</tr>
							</table>
		<h4>
			Instructions
		</h4>
		
					<div class="textPanel"><div class="textPanel" >
<h1>Project 2: Barrier Synchronization</h1>
<p><strong>Read</strong> this assignment description carefully before you begin. <strong>Start early</strong>, because you will be running performance experiments. You will need time to do the experiments and write a write-up after you finish coding, and most of the points for this assignment will come from the experiments and write-up so you'll want enough time to do a good job. Also, there are limited resources for running experiments and if everyone waits until the last week then there will be a lot of contention for these resources. (<em>You</em> are solely responsible for finishing on time - too much contention for experimental resources is not an excuse for lateness, so start early!)</p>
<p>&nbsp;</p>
<h2>Overview</h2>
<p>The goal of this assignment is to introduce OpenMP, MPI, and barrier synchronization concepts. You will implement several barriers using OpenMP and MPI, and synchronize between multiple threads and machines. You may work in groups of 2, and will document the individual contributions of each team member in your project write-up. (You may use Piazza to help you find a partner.)</p>
<p>OpenMP allows you to run parallel algorithms on shared-memory multiprocessor/multicore machines. For this assignment you will implement two spin barriers using OpenMP. MPI allows you to run parallel algorithms on distributed memory systems, such as compute clusters or other distributed systems. You will implement two spin barriers using MPI. Finally, you will choose one of your OpenMP barrier implementations and one of your MPI barrier implementations, and combine the two in an MPI-OpenMP combined program in order to synchronize between multiple cluster nodes that are each running multiple threads. (See the following figure.)</p>
<p><img alt="MPI-OpenMP combined barrier"  src="http://www.cc.gatech.edu/classes/AY2009/cs6210rkr_fall/projects/prj2_img.png" /></p>
<p>&nbsp;</p>
<p>You will run experiments to evaluate the performance of your barrier implementations. (Information about compute resources for running experiments is below.) You will run your OpenMP barriers on an 8-way SMP (symmetric multi-processor) system, and your MPI and MPI-OpenMP combined experiments on a 32-node dual-core cluster (32 nodes, and each node has two processor cores).</p>
<p>Finally, you will create a write-up that explains what you did, presents your experimental results, and most importantly, analyzes your results to explain the trends and phenomona you see. (Some hints for analysis are given below.)</p>
<p>&nbsp;</p>
<h2>Detailed Instructions</h2>
<p>These instructions are presented in a sequential order. However, depending on how you decide to divide the work with your project parter, you may choose do so some of these things in parallel. That is okay, so long as everything gets done, and you say who did what in your write-up.</p>
<h3>Part 1: Learn about OpenMP and MPI</h3>
<p>The first thing you want to do is learn how to program, compile, and run OpenMP and MPI programs.</p>
<p>You can compile and run OpenMP programs on any linux machine that has gomp installed. All the CoC Red Hat Enterprise Linux systems should have it (I believe). You can try the example code attached to this assignment (openmp.tar.gz), as well as looking at the following informational resources:</p>
<ul>
    <li><a  href="http://www.openmp.org/"    target="_blank">OpenMP Website</a></li>
    <li><a  href="http://www.openmp.org/specs/mp-documents/cspec20.pdf"    target="_blank">OpenMP Specification</a></li>
    <li><a  href="http://www.llnl.gov/computing/tutorials/openMP/"    target="_blank">Introduction to OpenMP</a></li>
</ul>
<p>You can compile and run MPI programs on any linux machine that has openmpi installed. (mpich is another MPI implementation, but we'll be using openmpi for this project. Note: <em>openmpi != OpenMP</em> !!) Unfortunately, most CoC systems do <em>not</em> have either openmpi or mpich installed. That is why we have allocated some cluster nodes for you. Details about using the cluster nodes are below. You can try running the example code attached to this assignment (mpi.tar.gz) on any of the development &amp; testing nodes, as well as looking at the following informational resources:</p>
<ul>
    <li><a  href="http://www.open-mpi.org/"    target="_blank">OpenMPI Website</a></li>
    <li><a  href="http://www.mpi-forum.org/"    target="_blank">MPI v2 Specification</a></li>
</ul>
<h3>Part 2: Develop OpenMP Barriers</h3>
<p>Implement <strong>two spin barriers using OpenMP</strong>. You may choose any two sping barriers you like. (For example, you could use ones from the MCS paper, anything covered in lecture, or any variation on these you think of.) Obviously, your barrier implementations cannot use the built-in OpenMP barrier! Although you can optionally use it as a third barrier in your experiments, as a baseline/control, if you choose.</p>
<h3>Part 3: Develop MPI Barriers</h3>
<p>Implement <strong>two spin barriers using MPI</strong>. At least one of these must be a <em>tree-based barrier</em> (if you choose to do both as tree-based barriers, that's okay too). If you choose, <em>one</em> of these may be the same algorithm you used for one of your OpenMP barriers, but the other one must be different. (However, even if you choose the same algorithm for one of them, you may find that you must implement it very differently using MPI than using OpenMP.) Obviously, your barrier implementations cannot use the built-in MPI barrier! Although you can optionally use it as a third barrier in your experiements, as a baseline/control, if you choose.</p>
<h3>Part 4: Develop MPI-OpenMP Combined Barrier</h3>
<p>Now choose one of the OpenMP barriers you implemented, and one of the MPI barriers you implemented. Combine them to create a barrier that synchronizes between multiple nodes that are each running multiple threads. (You'll want to be sure to preserve your original code for the two barriers too, so you can still run experiments on them seperately.)&nbsp; You can compare the performance of the combined barrier to your standalone MPI barrier.&nbsp; (Note that you will need to run more than one MPI process per node in the standalone configuration to make a comparable configuration to one multithreaded MPI process per node in the combined configuration, so that total number of threads is the same when you compare.)</p>
<h3>Part 5: Run Experiments</h3>
<p>The next step is to perform a performance evaluation of your barriers. You need to write a test harness that runs some OpenMP threads or MPI processes and synchronizes the threads/processes using your barrier implementation. Then your test harness should measure the performance of your barriers in a manner similar to the MCS paper. You should look at the experiments in that paper again and think about how they did them.</p>
<p>Measure your <em>OpenMP barriers on the Jedi cluster</em>, and <strong>scale the number of threads from 2 to 8</strong>. (1 thread is not really interesting for barriers, and more than 8 threads will show skewed results since the Jedi nodes only have 8 cores with which to provide true concurrency.)</p>
<p>Measure your <em>MPI barriers on the Whitestar cluster</em> (use the ones reserved for experiments only when you're ready to run for real and record your measurements; do not use the experiment only nodes at any other time, however). You should <strong>scale from 2 to 32 MPI processes</strong>, one process per Factor node. Then measure your MPI-OpenMP combined barrier, <strong>scaling from 2 to 32 MPI processes and running 2 OpenMP threads per process</strong>. (Running more than 2 OpenMP threads on Whitestar nodes will show skewed results since they only have 2 cores with which to provide true concurrency.)</p>
<p>Some things to think about in your experiments:</p>
<ul>
    <li>When scaling from X to Y of something, you don't need to run every single number between X and Y. However, you should run one at X and one at Y, of course, and enough in between to see any interesting trends or phenomona that occur. You'll have to decide at exactly what values you need to run the experiment in order to accomplish this. (Although if you have time and want to, you may run ever single number.)</li>
    <li>You will get skewed results if anyone else is using the system when you're trying to take measurements. This is because you never know when the system may context switch over to someone else's process for a while. That is why we are providing Jedi and Whitestar for you to run experiments. However, you will still have to share these with other students in the class, so please only use the Whitestar and Jedi nodes designated for experiments when you're going to take measurements for real. Use nodes designated for development and testing to develop and debug all your code before you run experiments. (For the OpenMP part, you may also be able to use your own machine or other Red Hat Enterprise Linux system in the CoC for development and testing.)</li>
    <li>You can use the gettimeofday() function to take timing measurements. See the man page for details about how to use it. You can also use some other method if you prefer, but explain in your write-up which measurement tool you used and why you chose it. Consider things like the accuracy of the measurement and the precision of the value returned.</li>
    <li>If you're trying to measure something that's too fast for your measurement tool (i.e.your tool is not precise enough), you can do it a bunch of times in a loop, measure the time to run the entire loop, and the divide by the number of iterations in the loop. This gives the average time for a single loop iteration. Think a moment about why that works, and how that increases the precision of your measurement.</li>
    <li>Finally, once you've chosen a measurement tool, think a bit about how you will take that measurement. You want to be sure you measure the right things, and exclude the wrong things from the measurement. You also want to do something to account for variation in the results (so, for example, you probably don't want to just measure once, but measure a bunch of times and take the average).</li>
</ul>
<h3>Part 6: Write-Up</h3>
<p>The last part to create the write-up. This should be either a PDF or MS-Word (.doc or .docx) file, and it should include a <em>minimum</em> of the following:</p>
<ul>
    <li>The names of both team members</li>
    <li>An introduction that provides an overview of what you did. (Do not assume the reader has already read this assignment description.)</li>
    <li>An explaination of how the work was divided between the team members (i.e. who did what)</li>
    <li>A description of the barrier algorithms that you implemented. (You do not need to go into as much implementation detail, with pseudocode and so forth, as the MCS paper did. However, you should include a good high-level description of each algorithm. You should <em>not</em> simply say that you implement algorighm X from the paper and refer the reader to the MCS paper for details.)</li>
    <li>An explaination of the experiments, including what experiments you ran, your experimental set-up, and your experimental methodology. (Give thorough details. Do not assume the reader has already read this assignment description.)</li>
    <li>Your experimental results. DO present your data using graphs. DO NOT use tables of numbers when a graph would be better. (Hint: a graph is usually better.) DO NOT include all your raw data in the write-up. (If you want to submit your raw data, you may include it in a separate file in your submission.) Compare both your OpenMP barriers. Compare both your MPI barriers. Present the results for your MPI-OpenMP barrier.</li>
    <li>An analysis of your experimental results. You should explain why you got the results that you did (think about the algorithm details, and the architecture of the machine you exerimented on). Explain any trends or interesting phenomona. If you see anything in your results that you did not expect, explain what you did expect to see and why your actual results are different from that. There should be at least a couple intersting points per experiment - the key is not explain not only the <em>what </em>of your results, but the <em>how</em> and <em>why</em> as well.</li>
    <li>A conclusion.</li>
</ul>
<p>&nbsp;</p>
<h2>Resources</h2>
<p>You have access to 4 Jedi nodes, which are 8-core SMP machines that you can use to run OpenMP code. You will only need to use one of these at a time, since you will not be doing any distributed computing on the Jedis (we have the Whitestar cluster for that).&nbsp; To access the Jedi nodes, ssh to one of the following (they are all .cc.gatech.edu machines - i.e. add .cc.gatech.edu to the node name) and log in with your OIT account:</p>
<ul>
    <li>jedi028 - experiments</li>
    <li>jedi047 - experiments</li>
    <li>jedi048 - experiments</li>
    <li>jedi061 - development/testing</li>
</ul>
<p>You also have access to the Whitestar cluster, which is a cluster of N-core SMP machines that you can use to run MPI and MPI/OpenMP combined code.&nbsp; To access the Whitestar cluster, you will first need to log in to a gateway node (whitestar.cc.gatech.edu) with your OIT account, and then you can ssh/scp/etc. from there to the cluster nodes.&nbsp; Parallel ssh (pssh) and scp (pscp) tools are installed on the gateway node to help you easily distribute your code across the cluster, and do other administrative things.&nbsp; (However, you will be launching your MPI code itself from one of the cluster nodes - do <em>not</em> use the gateway for running any code/computation.)&nbsp; The Whitestar cluster is divided into the following sub-clusters for you to use:</p>
<ul>
    <li>ws002 - ws010 (except ws005 which is down) - 8 nodes for development/testing</li>
    <li>ws011 - ws028 (except ws017 and ws018) - &quot;cluster 1&quot; 16 nodes for experiments</li>
    <li>ws029 - ws045 (except ws041) - &quot;cluster 2&quot; 16 nodes for experiments</li>
</ul>
<p>The attached hosts.tar.gz contains host files for each of these sub-clusters, so you can use them to drive your MPI on the appropriate part. It also includes a hosts file for all nodes in the entire Whitestar cluster (hosts_all) that you can use for administrative purposes (with pssh and pscp), but do <em>NOT</em> use it when launching an MPI application or it will attempt to use all three sub-clusters.&nbsp; You should only use hosts_devtest, hosts_cluster1, or hosts_cluster2 to launch an MPI app.</p>
<p>The Whitestar and Jedi nodes designated for dev/test are free for you to use any time for development and testing purposes. Note that since they are free to use you may be sharing them simultaneously with your classmates. So they'll be good for checking that your code is functioning properly, but you can't trust any experimental number that come from them.</p>
<p>The nodes designated for experiments will have a sign-up for times slots in the T-Square wiki. Please sign up for the times you want to use them in advance.&nbsp; Also, be kind and do not sign up for more than one time slot on Whitestar and one on Jedi at a time - if you need more time than that then you can sign up for more after your time slot has elapsed.&nbsp; Please be diligent about getting off promptly when your time is up.&nbsp; (You may also want to check that no one is still running things on your nodes when your time slot starts, before you launch your own experiment.)&nbsp; If you have a time slot that you've realized you aren't going to use, please remove yourself from the sign-up so that others can sign up for it; do this as early as you are sure you won't use it.&nbsp; (Also, by removing yourself, you may then sign up for a different time slot if you wish.)</p>
<p>Note that you will need to reserve both Whitestar cluster1 and cluster2 simultaneously at some point to scale up beyone 16 nodes.&nbsp; Please try to be thoughtful about how you do that and, for example, group all your experiments that require more than 16 nodes together and run them all then.&nbsp; Save experiments for 16 or fewer nodes for times when you only have one of the Whitestar experimental sub-clusters reserved, so that you haven't reserved nodes that you aren't using.</p>
<p>&nbsp;</p>
<h2>Submission Instructions</h2>
Please submit following results to T-square and also leave them in your home directory both on Clarke and Netlab. TA will collect all the result at deadline, and use them for grading.
<ul>
    <li>All your code (barrier implementations, experiment test harness, etc.)</li>
    <li>Makefile</li>
    <li>Anything else we may need to compile and run all your barriers</li>
    <li>Experimental data</li>
    <li>Your write-up, that includes all the things listed above (PDF)</li>
</ul>
</div></div>
		
																																	<h4>
				Additional resources for assignment
			</h4>	
				<ul class="attachList indnt1">
																		<li>
																	<img src = "/library/image/sakai/compressed.gif?panel=Main" border="0" alt="File attachment" />
																	<a href="https://t-square.gatech.edu/access/content/attachment/82397.201108/Assignments/2ca921e1-2e9f-4c0a-b1ab-d79e4ced0206/openmp.tar.gz" target="_blank">openmp.tar.gz</a>						
																	(1 KB)
															</li>
																								<li>
																	<img src = "/library/image/sakai/compressed.gif?panel=Main" border="0" alt="File attachment" />
																	<a href="https://t-square.gatech.edu/access/content/attachment/82397.201108/Assignments/02118f0e-d09e-477e-b8c2-674c648a4712/mpi.tar.gz" target="_blank">mpi.tar.gz</a>						
																	(1 KB)
															</li>
																								<li>
																	<img src = "/library/image/sakai/compressed.gif?panel=Main" border="0" alt="File attachment" />
																	<a href="https://t-square.gatech.edu/access/content/attachment/82397.201108/Assignments/3b9af907-8241-455e-b854-54a55d8ea314/hosts.tar.gz" target="_blank">hosts.tar.gz</a>						
																	(1 KB)
															</li>
															</ul>
										<hr class="itemSeparator" />
		<h3>Submission</h3>
					<form name="addSubmissionForm" action="https://t-square.gatech.edu/portal/tool/21dea42c-f6e6-409e-a1e3-4f69fd0b3088?panel=Main" method="post" onsubmit="return true;">
		<input type="hidden" name="eventSubmit_doRead_add_submission_form" value="x" />
		<input type="hidden" name="option" value="cancel" />
		<input type="hidden" name="assignmentId" value="/assignment/a/82397.201108/51bc87be-fc19-403d-81aa-274161d9cf18" />
																							<h4>
													This assignment allows submissions by attaching documents only.
											</h4>
								<h4>
					Attachments
				</h4>	
																					<p class="instruction">No attachments yet</p>
										<p class="act">
																																																								<input
											class="disableme" 
											type="button" 
											name="attach" 
											id="attach"
																							value="Add Attachments"
																						accesskey="a" 											onclick="document.addSubmissionForm.onsubmit();document.addSubmissionForm.option.value='attach'; document.addSubmissionForm.submit(); return false;"
										/>
																																			</p>
																																							<div class="act">
																										<input
								type="button"
								class="active"
																								name="post"
								accesskey="s"
								id="post" 
								value="Submit"
								onclick="document.addSubmissionForm.onsubmit();showNotif('submitnotif','post','addSubmissionForm'); document.addSubmissionForm.option.value='post'; document.addSubmissionForm.submit(); return false;"
							/>
							<input
								class="disableme" 
								type="button" 
								name="preview" 
								accesskey="v"
								id="preview" 
								value="Preview"
								onclick="document.addSubmissionForm.onsubmit();showNotif('submitnotif','preview','addSubmissionForm');document.addSubmissionForm.option.value='preview'; document.addSubmissionForm.submit(); return false;"
							/>
							<input
								class="disableme" 
								type="button" 
								name="save" 
								accesskey="d"
								id="save" 
								value="Save Draft"
								onclick="document.addSubmissionForm.onsubmit();showNotif('submitnotif','save','addSubmissionForm');document.addSubmissionForm.option.value='save'; document.addSubmissionForm.submit(); return false;"
							/>
							<input 
								class="disableme"
								type="button" 
								name="cancel"
								accesskey="x"
								id="cancel" 
								value="Cancel"
								onclick="document.addSubmissionForm.onsubmit();document.addSubmissionForm.option.value='cancel'; document.addSubmissionForm.submit(); return false;"
							/>
																			<span id="submitnotif" style="visibility:hidden">Processing......</span>
			</div>
			</form>
	</div>

</body></html>